import java.util.ArrayList;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-04-11
 * Time: 11:35
 */
public class Main3 {
    //快速排序时间
    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arrayList=new ArrayList<>();
        if (input == null || k == 0) {
            return arrayList;
        }
        quickSort(input, 0, input.length - 1);
        for(int i=0;i<k;i++){
            arrayList.add(input[i]);
        }
        return arrayList;
    }
    private static void quickSort(int[] input,int start,int end){
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int pivot = input[(start + end) / 2];
        while (left <= right) {
            while (left <= right && input[right] > pivot) {
                --right;
            }
            while (left <= right && input[left] < pivot) {
                ++left;
            }
            if (left <= right) {
                int tmp = input[left];
                input[left] = input[right];
                input[right] = tmp;
                ++left;
                --right;
            }
        }
        quickSort(input, start, right);
        quickSort(input, left, end);
    
    }
    public static void main(String[] args) {
        int[] input = {4,5,1,6,2,7,3,8};
        ArrayList<Integer> list = GetLeastNumbers_Solution(input, 4);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        
    }
}

